package kaiao.dynamic;

public class 打家劫舍 {

	public static void main(String[] args) {

	}

	// 动态规划， 1 。定义子问题，规模较小的问题，类似于找规律，找到状态转移方程
	// 2.两种分析方式 1.从小基数开始看规律 2.从n开始看与n-1 和 n-2的规律
	// 3.记得从0开始看，避免出错
	public int rob(int[] nums) {

		// 从n开始看
		/**
		 * dp[n+1] 其实是要计算 dp[n] ? < dp[n-1] + num
		 */
		int n = nums.length;

		// 初始化结果计算数组
		int[] dp = new int[n+1];

		// 初始化最小数组，从0开始，避免混乱
		dp[0] = 0;
		dp[1] = nums[0];

		// 动态计算结果
		for (int i = 2; i < n + 1; i++) {
			dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
		}

		return dp[n];
	}
}
